package week02

// 684. 冗余连接
// https://leetcode-cn.com/problems/redundant-connection/

func findRedundantConnection(edges [][]int) []int {
	// 构造图
	var graph = make(map[int][]int)
	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		graph[edge[1]] = append(graph[edge[1]], edge[0])

		// 检查是否出现环
		var visit = make(map[int]struct{})
		visit[edge[0]] = struct{}{}
		if hasCircle(graph, visit, edge[0], -1) {
			return edge
		}
	}
	return []int{}
}

func hasCircle(graph map[int][]int, visit map[int]struct{}, cur, parent int) bool {
	for _, next := range graph[cur] {
		if next == parent {
			continue
		}
		if _, ok := visit[next]; ok {
			return true
		}
		visit[next] = struct{}{}
		if hasCircle(graph, visit, next, cur) {
			return true
		}
		delete(visit, next)
	}
	return false
}
